package BFS.解决最短路径;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Date 2024/9/9 21:33
 * @description: 离入口最近的出口
 * .    https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
 * @Author LittleNight
 */
public class likou1926 {

    // BFS (队列, 层序遍历) 解决最短路问题
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] vis = new boolean[101][101];
    int m, n;
    public int nearestExit(char[][] maze, int[] entrance) {
        // 只需要一次 bfs 即可
        m = maze.length; n = maze[0].length;
        int step = 0; // 记录步数
        int i = entrance[0], j = entrance[1];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        vis[i][j] = true; // 标记已经访问过

        // bfs 主逻辑
        while(!queue.isEmpty()) {
            int sz = queue.size(); // 记录同时要弹出的数量
            for (int z = 0; z < sz; z++) {
                int[] poll = queue.poll(); // 弹出队列的头元素
                int a = poll[0], b = poll[1];
                // 加入下一层. 那么步数也加 1
                step++;
                for (int k = 0; k < 4; k++) {
                    int x = a + dx[k], y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.') {
                        // 加入之前先进行判断一下是不是到入口了
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        queue.offer(new int[]{x, y});
                        vis[x][y] = true; // 标记访问过
                    }
                }
            }
        }
        return step;
    }

}
